package greed;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class partitionLabels {
    public List<Integer> partitionLabels(String s) {
        //存放字符和对应的index
        HashMap<Character,Integer> map = new HashMap();
        ArrayList<StringBuffer> list = new ArrayList();
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(!map.containsKey(c)){
                StringBuffer sb = new StringBuffer();
                sb.append(c);
                list.add(sb);
                map.put(c, list.size()-1);
            }else{
                Integer index = map.get(c);
                //需要合并
                StringBuffer stringBuffer = list.get(index);
                for(int j=index+1;j<list.size();j++){
                    //还要更新map中涉及到的index以及删除list中无用的
                    StringBuffer sb = list.get(j);
                    for(int k=0;k<sb.length();k++){
                        map.put(sb.charAt(k), index);
                    }
                    stringBuffer.append(sb);
                    // list.remove(j);
                }
                //得倒着来删除
                int size = list.size();
                for(int j=index+1;j<size;j++){
                    list.remove(list.size()-1);
                }
                stringBuffer.append(c);
                list.set(index, stringBuffer);
            }
        }
        ArrayList<Integer> rs = new ArrayList<>(list.size());
        for(StringBuffer sb : list){
            rs.add(sb.length());
        }
        return rs;
    }
    public static void main(String[] args) {
        partitionLabels obj = new partitionLabels();
        // String s = "ababcbacadefegdehijhklij";
        // String s = "eccbbbbdec";
        String s = "aebbedaddc";
        List<Integer> rs = obj.partitionLabels(s);
        for (Integer r : rs) {
            System.out.println(r);
        }
    }
}
